package paixu;

public class nixudui2 {
	   public static void main(String[] args) {
	        int[] arr = new int[]{1,3,4,5,2};
	        System.out.println(invertedOrderNum(arr));
	    }

	    public static int invertedOrderNum(int[] arr) {
	        if (arr == null || arr.length < 2) {
	            return 0;
	        }
	        return process(arr, 0, arr.length - 1);
	    }

	    public static int process(int[] arr, int l, int r) {
	        if (l == r) {
	            return 0;
	        }
	        int mid = l + ((r - l) >> 1);
	        return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
	    }

	    private static int merge(int[] arr, int l, int mid, int r) {
	        int[] help = new int[r - l + 1];
	        int i = 0;
	        int p1 = l;
	        int p2 = mid + 1;
	        int res = 0;
	        while (p1 <= mid && p2 <= r) {
	            res += arr[p1] <= arr[p2] ? 0 : (mid - p1 + 1);
	            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
	        }
	        while (p1 <= mid) {
	            help[i++] = arr[p1++];
	        }
	        while (p2 <= r) {
	            help[i++] = arr[p2++];
	        }
	        for (i = 0; i < help.length; i++) {
	            arr[l + i] = help[i];
	        }
	        return res;
	    }
	    
}
